1. Field of the Invention
The present invention relates to an associatively operated storage arrangement having a main memory which serves to accommodate data in the form of an associative component and a non-associative component, a comparator device serving to compare the associative part of the read-out data with a search word, address converters serving to derive the storage addresses from the association word or from a search word or from parts of these words, and an extension counter whose count influences the address derivation and is increased by one whenever an initially addressed storage position proves otherwise engaged.
2. Description of the Prior Art
The German published application No. 2,319,468 discloses a storage device comprising a plurality of storage banks which, in turn, comprise a plurality of storage positions, which are in each case classified into an associative section which can be addressed by one part (prefix) of an association word, and into a non-associative section which serves to accommodate an assigned word, where each storage bank is assigned address converters serving to derive the addresses from the association word in a manner which differs from storage bank to storage bank and having a pseudo-statistical distribution in such a manner that the prefix lines which connect the storage positions to one another form irregular lines, each storage position being able to be addressed by specific prefixes. All of the contents on a prefix line are read-out simultaneously.
A chance accumulation of association words having the same prefix can give rise to the situation that the storage positions available along a prefix line are not sufficient for the entry of the words. Therefore, the storage device is provided with an extension counter, the relevant count of which co-determines the formation of the addresses and is increased by one whenever a new entry of a word having a specific prefix is to be made and all the storage positions along the relevant prefix line are already in use. Thus, with the aid of the extension counter, additional addressing planes are provided which are capable of accommodating extensions of prefix line.
A possibility of surveying the state of seizure along a prefix line considerably simplifies the allocation of free storage positions for new entries. When 8 storage banks are employed in the storage device, when the memory is up to approximately 70% full, only in a few cases will it be necessary to conduct a second search cycle to indicate a free storage position. Not until the store is approximately 95% full will, on the average, two search cycles be required triggered.